Analysis of the Fibonacci Sequence

Hello there, In this post, I will try to analyze the Fibonacci sequence Our problem in here is finding the nth Fibonacci number of the Fibonacci sequence.
For example, let's find the 6th number in the Fibonacci sequence. It is 8

1 1 2 3 5 8 13 21 34 55

Naive Approach - O((1.618)^N)

We will need help from our friend recursion for writing the function for solving our problem. So the following will we be our cheat sheet for writing python code.

fib(1) = 1
fib(2) = 1
fib(N) = fib(N-1)+fib(N-2)

def fibFinder(n):
  if n == 1 or n == 2:
    return 1
  return fibFinder(n-1)+fibFinder(n-2)

It looks like cheat sheet right? We just need to call our function like fibFinder(n) and it will return nth Fibonacci number.

Figure 1: The representation of recursion path of Fibonacci 6

Dynamic Approach - O(N)

Our problem is needlessly going down in the tree by using our recursion function. Our recursion function will calculate fib(4) and fib(5) for calculating fib(6). fib(5) will calculate fib(4) and fib(3). In this case, we have two fib(4) calculation and this is redundant. What can we do for this problem? OMG, yes! I thought the same. Let's keep calculated values in the list. If the number is calculated previously, we just need to take it from the list. If it is not on the list, let's calculate it and put it on to the list.

# recursive version
def fibFinder(n, l):
    # if n is 1 or 2 return 1 as initially.
    if n == 1 or n == 2:
        l[n] = 1
        return l[n]
    elif l[n] == -1:
        l[n] = fibFinder(n-1, l) + fibFinder(n-2, l) # Calculate it if this n value is not calculated before.
    return l[n]
# fibFinder(n, [-1]*(n+1))

As we can see in the code, this is the recursive implementation of the Fibonacci sequence. We need to define a list and store our values inside of that list. Another negative side of this function is recursive calls go into the stack. Therefore, the stack might overflow. To solve this problem we can use the iterative version of it.

Let us see the iterative version of the same algorithm. This version is also running at O(N).

def fibFinder(n):
  numOne, numTwo = 1, 1
  for i in range(n-2):
    numOne, numTwo = numTwo, numOne+numTwo
  return numTwo

So, this solves our problem pretty fast ha? Can we perform better than O(n)?

Matrix Multiplication Approach - O(log₂(N))

We can represent Fibonacci sequence as matrix multiplication. Let's consider the following example.

We know that Fib(3) is equal to Fib(2)+Fib(1). So let's write next equation.

Moreover, we know that Fib(4) is equal to Fib(2)+Fib(3). Can we write general formula from these equations? Well, the answer is hell yeah.

So know we have a general formula for finding Nth fibonacci number. However, how do we have O(log₂(N)) solution? Answer is easy. For Nth power we calculate N/2 power and multiply them. Lets consider the following example.

Let's assume we want to find n=10, n=21 and n=56. Furthermore, do not forget we get the (n+2)th Fibonacci number. Because we already know Fib(1) and Fib(2) is equal to 1.

n = 10

We only need to calculate a² and a⁵. After our calculation, we just need to multiply it by itself.

n = 21

We only need to calculate a², a⁵ and a¹⁰.

n = 56

We only need to calculate a², a⁵, a¹¹ and a²³.
Therefore, we can write following python code after this knowledge. Plus, it runs in O(log₂(N)) and this is the best side of this algorithm.

# This function makes the initial call for the power function.
def fibFinder(n):
    if n == 1 or n == 2:
        return 1

    poweredMatrix = power(n-2)

    # Multiplying poweredMatrix(M) with [1,1], which are fib(1) and fib(2), is equal to M[0][0] + M[0][1]
    returnVal = poweredMatrix[0][0] + poweredMatrix[0][1]

    return returnVal


def power(n):
    # Return our primary matrix([[1,1],[1,0]]) when we hit the bottom of the recurence.
    if n == 1:
        return [[1, 1], [1, 0]]

    # In each call assign returned value to K
    K = power(int(n / 2))

    # Multiply K by itself
    K = multiply(K, K)

    # If we consider
    if n % 2 != 0:
        K = multiply(K, [[1, 1], [1, 0]])
    return K


# This function does the matrix multiplication.
def multiply(N, M):
    a = N[0][0] * M[0][0] + N[0][1] * M[1][0]
    b = N[0][0] * M[0][1] + N[0][1] * M[1][1]
    c = N[0][1] * M[0][0] + N[1][1] * M[1][0]
    d = N[0][1] * M[0][1] + N[1][1] * M[1][1]
    return [[a, b], [c, d]]

# print(fibFinder(100000))